Processing images for motion pictures or otherwise can include identifying objects in one or more frames. The objects can be identified by determining object boundaries. An object boundary can be identified using rotoscoping. Rotoscoping includes tracing boundaries of objects in a motion picture frame-by-frame via digital means. Rotoscoping can extract digital mattes to allow special effects and other image processing to be applied to the image. Examples of special effects include replacing objects in a scene with other objects generated via a computer, compositing an actor from one scene to another, and changing a two-dimensional (2D) motion picture to a three-dimensional (3D) motion picture. Examples of other image processes include tracking an object in an image sequence and tracking an object in a left and right eye image sequence.
Rotoscoping can be used when other techniques, such as a blue screen method, fail to produce a matte within an acceptable accuracy tolerance. For example, images may include a complex background, such as images using archival footage, for which a blue screen method may fail to produce acceptable results. Rotoscoping can be labor-intensive. Semiautomatic rotoscoping techniques can be used for efficiency. Such techniques include contour-based methods and alpha-channel algorithms.
Contour-based methods can involve a user that specifies a contour in one or more frames and as accurately as possible. The contour is a rough estimate of an object boundary. An energy function is evaluated and an active contour is associated with the boundary based on the rough estimate contour. The energy function is minimized iteratively, producing an optimal contour around the object. In some contour-based methods, stroke matching is performed that includes analyzing cost functions to determine which strokes match certain contours of objects between key frames. The algorithms can output relatively smooth contours and establish correspondence between contours in neighboring frames, but often require a skilled user to delineate an object of interest.
Alpha-channel algorithms can extract soft boundaries of objects by analyzing three regions of color: foreground with respect to the object, background with respect to the object, and blended foreground and background in an intermediate region along a boundary of the object. Alpha-channel algorithms often are applied to individual frames, although application to sequences is also possible.
Alpha-channel algorithms can extract soft boundaries, as well as the alpha value, or transparency, of the value. In some alpha-channel algorithms, a Bayesian approach is applied that models both the foreground and background color distributions with spatially varying sets of Gaussians and that assumes a fractional blending of the foreground and background colors to produce a final output. Other alpha-channel algorithms assume that a clean foreground color is a linear combination of a set of clusters and calculate the color and alpha values by examining pairs of clusters in the foreground and the background.
Still other alpha-channel algorithms perform one or more of: (i) estimate the alpha matte in high resolution images and image sequences by assuming that the clusters are prolate, or cigar-shaped, in the red, green, blue (RGB) color space; (ii) derive a cost function from local smoothness assumptions on foreground and background colors and obtaining a quadratic cost function in terms of alpha by analytically eliminating foreground and background colors; (iii) derive a partial differential equation that relates the gradient of an image to the alpha values and describe an efficient algorithm, providing the alpha values as the solution of the equation; (iv) formulate the problem of natural image matting as one of solving Poisson equations with the matte gradient field and extract mattes using a pair of flash/no-flash images, referred to as “flash matting”; (v) allow construction of environment mattes “on-the-fly,” without a need for specialized calibration; (vi) perform environment matting by capturing a description of how the object refracts and reflects light, in addition to capturing foreground objects and the alpha matte, and by placing the foreground object in a new environment using environment compositing. Such alpha-channel algorithms, however, seek to produce soft segmentations without producing hard segmentations, which can result in segmentation that is more accurate.
Another rotoscoping technique is random walks. Random walks is a graphical image segmentation algorithm that attempts to identify a probability that a random walker, starting at some “seed” pixel and traveling to some “sink” pixel, would cross a particular pixel. Edges between pixels can be weighted such that pixels considered similar by some criteria have low edge weights, making it more likely for the walker to cross that edge. Probabilities can be determined as a solution to a combinatorial Dirichlet problem. Random walks can also use Locality Preserving Projections to transform a colorspace so that similar colors, such as those in slow-varying gradients, can be brought together and dissimilar colors can be moved apart. Random walks, however, may be unable to segment images cleanly in the presence of noise, resulting in inaccurate object boundary identifications.
Accordingly, methods, devices, and systems are desired that can identify boundaries of objects efficiently and accurately. Methods, devices and systems are also desirable that can produce hard segmentations and identify object boundaries accurately in the presence of noise.